{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #单词的压缩编码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumLengthEncoding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词的压缩编码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>单词数组&nbsp;<code>words</code> 的 <strong>有效编码</strong> 由任意助记字符串 <code>s</code> 和下标数组 <code>indices</code> 组成，且满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>words.length == indices.length</code></li>\n",
    "\t<li>助记字符串 <code>s</code> 以 <code>&#39;#&#39;</code> 字符结尾</li>\n",
    "\t<li>对于每个下标 <code>indices[i]</code> ，<code>s</code> 的一个从 <code>indices[i]</code> 开始、到下一个 <code>&#39;#&#39;</code> 字符结束（但不包括 <code>&#39;#&#39;</code>）的 <strong>子字符串</strong> 恰好与 <code>words[i]</code> 相等</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定一个单词数组&nbsp;<code>words</code> ，返回成功对 <code>words</code> 进行编码的最小助记字符串 <code>s</code> 的长度 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [&quot;time&quot;, &quot;me&quot;, &quot;bell&quot;]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>一组有效编码为 s = <code>&quot;time#bell#&quot; 和 indices = [0, 2, 5</code>] 。\n",
    "words[0] = &quot;time&quot; ，s 开始于 indices[0] = 0 到下一个 &#39;#&#39; 结束的子字符串，如加粗部分所示 &quot;<strong>time</strong>#bell#&quot;\n",
    "words[1] = &quot;me&quot; ，s 开始于 indices[1] = 2 到下一个 &#39;#&#39; 结束的子字符串，如加粗部分所示 &quot;ti<strong>me</strong>#bell#&quot;\n",
    "words[2] = &quot;bell&quot; ，s 开始于 indices[2] = 5 到下一个 &#39;#&#39; 结束的子字符串，如加粗部分所示 &quot;time#<strong>bell</strong>#&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [&quot;t&quot;]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>一组有效编码为 s = &quot;t#&quot; 和 indices = [0] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 2000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 7</code></li>\n",
    "\t<li><code>words[i]</code> 仅由小写字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 820&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/short-encoding-of-words/\">https://leetcode-cn.com/problems/short-encoding-of-words/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [iSwD2y](https://leetcode.cn/problems/iSwD2y/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [iSwD2y](https://leetcode.cn/problems/iSwD2y/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"time\",\"me\",\"bell\"]', '[\"t\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for k in range(1,len(word)):\n",
    "                good.discard(word[k:])\n",
    "        return sum(len(word)+1 for word in good)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for k in range(1, len(word)):\n",
    "                good.discard(word[k:])\n",
    "\n",
    "        return sum(len(word) + 1 for word in good)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for k in range(1, len(word)):\n",
    "                good.discard(word[k:])\n",
    "\n",
    "        return sum(len(word) + 1 for word in good)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for k in range(1, len(word)):\n",
    "                good.discard(word[k:])\n",
    "\n",
    "        return sum(len(word) + 1 for word in good)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        res = [words[0]]\n",
    "        for i in range(1, len(words)):\n",
    "            n1 = len(words[i])\n",
    "            flag = True\n",
    "            for j in range(len(res)):\n",
    "                n2 = len(res[j])\n",
    "                if n1 >= n2 and words[i][-n2:] == res[j]:\n",
    "                    res[j] = words[i]\n",
    "                    flag = False\n",
    "                    break\n",
    "                if n1 < n2 and words[i] == res[j][-n1:]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                res.append(words[i])\n",
    "        return len(''.join(res)) + len(res)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda x:x[::-1])\n",
    "        a=set(words)\n",
    "        ans=0\n",
    "        for word in words:\n",
    "            n=len(word)\n",
    "            for i in range(1,n):\n",
    "                a.discard(word[i:])\n",
    "        \n",
    "        return sum(len(a1)+1 for a1 in a)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for k in range(1, len(word)):\n",
    "                good.discard(word[k:])\n",
    "\n",
    "        return sum(len(word) + 1 for word in good)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for k in range(1, len(word)):\n",
    "                good.discard(word[k:])\n",
    "\n",
    "        return sum(len(word) + 1 for word in good)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        if len(words) == 1:\n",
    "            return len(words[0]) + 1\n",
    "        if not words:\n",
    "            return 0\n",
    "\n",
    "        max_lengths = []\n",
    "        while words:\n",
    "            now_word = words[0]\n",
    "            now_word_index = 0\n",
    "            index = 1\n",
    "            while index < len(words):\n",
    "                word = words[index]\n",
    "                # 是结尾\n",
    "                if now_word.endswith(word):\n",
    "                    words.pop(index)\n",
    "                    continue\n",
    "                # 以被选为结尾\n",
    "                if word.endswith(now_word):\n",
    "                    now_word = word\n",
    "                    words.pop(now_word_index)\n",
    "                    now_word_index = index - 1\n",
    "                    continue\n",
    "                # 啥也不是\n",
    "                index += 1\n",
    "            max_lengths.append(now_word)\n",
    "            words.pop(now_word_index)\n",
    "        return sum(list(map(len, max_lengths))) + len(max_lengths)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key = lambda x : x[: :-1], reverse = True)\n",
    "        tmp = []\n",
    "        for w in words:\n",
    "            if not tmp:\n",
    "                tmp.append(w)\n",
    "            else:\n",
    "                if w == tmp[-1][-len(w):]:\n",
    "                    continue\n",
    "                else:\n",
    "                    tmp.append(w)\n",
    "        return sum(len(t) + 1 for t in tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for k in range(1, len(word)):\n",
    "                good.discard(word[k:])\n",
    "\n",
    "        return sum(len(word) + 1 for word in good)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        res = 0\n",
    "        for i in range(0,len(words)):\n",
    "            words[i] = words[i][::-1]\n",
    "        words.sort()\n",
    "        print(words)\n",
    "        past = ''\n",
    "        length = 0\n",
    "        for i in range(0,len(words)):\n",
    "            if words[i][0:length] != past:\n",
    "                res += length + 1\n",
    "            past = words[i]\n",
    "            length = len(past)\n",
    "        res += length + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        endlist, check = [], 0\n",
    "        for i in words:\n",
    "            for j in endlist:\n",
    "                if i == j:\n",
    "                    check = 1\n",
    "                    continue\n",
    "                elif i in j and i[-1] == j[-1]:\n",
    "                    check = 1\n",
    "                    continue\n",
    "                elif j in i and i[-1] == j[-1]:\n",
    "                    endlist.remove(j)\n",
    "            if check == 0:\n",
    "                endlist.append(i)\n",
    "            check = 0\n",
    "        num = 0\n",
    "        for i in endlist:\n",
    "            num += (1+len(i))\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            good = set(words)\n",
    "            for word in words:\n",
    "                for k in range(1, len(word)):\n",
    "                    good.discard(word[k:])\n",
    "            return sum(len(word) + 1 for word in good)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = sorted(w[:: -1] for w in words)\n",
    "        return sum(map(len, words)) + len(words) - sum(len(words[i]) + 1 for i, w in enumerate(words[1: ]) if w.startswith(words[i]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        # 哈希集合、后缀、求字串\n",
    "        '''\n",
    "存储不是其他单词后缀的单词,统计单词长度加一的和\n",
    "\n",
    "先将所有单词存储到哈希集合中，然后通过枚举单词的后缀单词删除是其他单词后缀的单词，最后统计长度和\n",
    "        '''\n",
    "        \n",
    "        hashset = set()\n",
    "        for word in words:\n",
    "            hashset.add(word)\n",
    "        #print(\"--\",hashset)\n",
    "        n = len(words)\n",
    "        for i in range(n):\n",
    "            for j in range(1, len(words[i])):\n",
    "                if words[i][j:] in hashset:\n",
    "                    hashset.remove(words[i][j:])\n",
    "        ans = 0\n",
    "        for i in hashset:\n",
    "            ans += len(i) + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for k in range(1, len(word)):\n",
    "                good.discard(word[k:])#descard，从集合中取出元素\n",
    "\n",
    "        return sum(len(word) + 1 for word in good)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        res = []\n",
    "        for word in words:\n",
    "            flag = True\n",
    "            for idx, target in enumerate(res):\n",
    "                if target.endswith(word):\n",
    "                    flag = False\n",
    "                    break\n",
    "                if word.endswith(target):\n",
    "                    res[idx] = word\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                res.append(word)\n",
    "        print(res)\n",
    "        return sum(len(s) for s in res) + len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        wd=set(words)\n",
    "        for t in words:\n",
    "            l=len(t)\n",
    "            for j in range(1,l):\n",
    "                if t[l-j:] in wd:\n",
    "                    wd.remove(t[l-j:])\n",
    "        print(wd)\n",
    "        return len('#'.join(list(wd))+'#')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key = lambda x:x[:: -1])\n",
    "        ans = len(words[-1]) + 1\n",
    "        for i in range(len(words)-1):\n",
    "            if words[i] != words[i+1][len(words[i+1])-len(words[i]):]:\n",
    "                ans+=len(words[i])+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        load = set(words)\n",
    "        \n",
    "        for v in words:\n",
    "            for vv in range(1, len(v)):\n",
    "                load.discard(v[vv:])\n",
    "        return sum(len(v) + 1 for v in load)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        us = set(words)\n",
    "        for word in words:\n",
    "            for i in range(1, len(word)):\n",
    "                suffix = word[i: ]\n",
    "                us.discard(suffix)\n",
    "        \n",
    "        res = 0\n",
    "        for w in us:\n",
    "            res += len(w)\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key = len)\n",
    "        res = []\n",
    "        for cnt, w in enumerate(words):\n",
    "            if not any(w1.endswith(w) for w1 in words[cnt+1:]): res.append(w)\n",
    "        return len(res) + len(''.join(res))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        new_words = copy.copy(words)\n",
    "        new_words = list(map(lambda x: x[::-1], new_words))\n",
    "        new_words.sort()\n",
    "\n",
    "        i = 0\n",
    "        while i < len(new_words) - 1:\n",
    "            if new_words[i + 1].startswith(new_words[i]):\n",
    "                new_words.pop(i)\n",
    "            else:\n",
    "                i += 1\n",
    "        \n",
    "        new_len = list(map(len, new_words))\n",
    "        return sum(new_len) + len(new_len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        if len(words)==0:\n",
    "            return 0\n",
    "        #\n",
    "        words = list(set(words))\n",
    "        temp_words = copy.deepcopy(words)\n",
    "        words_n = len(words)\n",
    "        for i in range(words_n):\n",
    "            now_word = words[i]\n",
    "            for j in range(len(temp_words)):\n",
    "                if now_word in temp_words[j] and now_word ==temp_words[j][-len(now_word):] and now_word != temp_words[j]:\n",
    "                    # print(now_word,'temp_words[j][-len(now_word):]-',temp_words[j][-len(now_word):])\n",
    "                    temp_words.remove(now_word)\n",
    "                    break\n",
    "            #\n",
    "        #\n",
    "        s =\"\"\n",
    "        for word in temp_words:\n",
    "            s+=word +\"#\"\n",
    "        return len(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        hashset = set()\n",
    "        for word in words:\n",
    "            hashset.add(word)\n",
    "        n = len(words)\n",
    "        for i in range(n):\n",
    "            for j in range(1, len(words[i])):\n",
    "                if words[i][j:] in hashset:\n",
    "                    hashset.remove(words[i][j:])\n",
    "        ans = 0\n",
    "        for i in hashset:\n",
    "            ans += len(i) + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        goods = set(words)\n",
    "        for word in words:\n",
    "            # 删除后缀\n",
    "            for j in range(1, len(word)):\n",
    "                goods.discard(word[j:])\n",
    "        return sum([len(good) + 1 for good in goods])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key= lambda x:x[::-1],reverse = True)\n",
    "        res = []\n",
    "        for word in words:\n",
    "            if res and res[-1][-len(word):] == word:\n",
    "                continue\n",
    "            else:\n",
    "                res.append(word)\n",
    "        return sum(len(i) + 1 for i in res )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for k in range(1, len(word)):\n",
    "                good.discard(word[k:])\n",
    "\n",
    "        return sum(len(word) + 1 for word in good)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        good = set(words)\n",
    "        for word in words:\n",
    "            for i in range(1, len(word)):\n",
    "                good.discard(word[i:])\n",
    "        return sum([len(word) + 1 for word in good])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words_set = set(words)\n",
    "        ans_str = ''\n",
    "        ans_set = set()\n",
    "        for  word in words_set:\n",
    "            is_append = False\n",
    "            for  ans in words_set:\n",
    "                if word != ans and len(ans) > len(word) and ans[-len(word):] == word:  #找到\n",
    "                    is_append = True\n",
    "                    break\n",
    "            if not is_append:\n",
    "                ans_set.add(word)\n",
    "                ans_str += word + '#'\n",
    "        print(ans_str)\n",
    "        return len(ans_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        s=''\n",
    "        words.sort(key=lambda x: len(x),reverse=True)\n",
    "        for i in words:\n",
    "            if not re.search(i+'#',s):\n",
    "                s+=i+'#'\n",
    "        return len(s)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        s=''\n",
    "        words.sort(key=lambda x: len(x),reverse=True)\n",
    "        for i in words:\n",
    "            if not re.search(i+'#',s):\n",
    "                s+=i+'#'\n",
    "        return len(s)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        def quick_sort(sort_list, start, end):\n",
    "            if start>=end:\n",
    "                return\n",
    "            high, low, mid = end, start, sort_list[start]\n",
    "            while high > low:\n",
    "                while high > low and len(sort_list[high]) <= len(mid):\n",
    "                    high -= 1\n",
    "                sort_list[low] = sort_list[high]\n",
    "                while high > low and len(sort_list[low]) > len(mid):\n",
    "                    low += 1\n",
    "                sort_list[high] = sort_list[low]\n",
    "            sort_list[low] = mid\n",
    "            quick_sort(sort_list, start, low-1)\n",
    "            quick_sort(sort_list, low+1, end)\n",
    "        \n",
    "        quick_sort(words, 0, len(words)-1)\n",
    "        record = \"\"\n",
    "        for w in words:\n",
    "            w+=\"#\"\n",
    "            if w in record:\n",
    "                continue\n",
    "            record += w\n",
    "        return len(record)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = sorted(words, key=lambda x: -len(x))\n",
    "\n",
    "        map = set()\n",
    "        res = 0\n",
    "        for word in words:\n",
    "            if word not in map:\n",
    "                res += len(word) + 1\n",
    "                for i in range(len(word)):\n",
    "                    map.add(word[i:])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda x: len(x), reverse=True)\n",
    "        suffixes = set()\n",
    "        min_len = 0\n",
    "        for i in range(len(words)):\n",
    "            if words[i] in suffixes:\n",
    "                continue\n",
    "            for j in range(len(words[i])):\n",
    "                suffixes.add(words[i][j:])\n",
    "            min_len += len(words[i]) + 1\n",
    "        return min_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=len, reverse=True)\n",
    "        result, trie = 0, {}\n",
    "        for w in words:\n",
    "            cur, flag = trie, False\n",
    "            for c in reversed(w):\n",
    "                if not c in cur:\n",
    "                    flag = True\n",
    "                cur = cur.setdefault(c, {})\n",
    "            if flag:\n",
    "                result += len(w) + 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = {}\n",
    "        for word in words:\n",
    "            n = len(word)\n",
    "            node = trie\n",
    "            for i in range(n-1, -1,-1):\n",
    "                if word[i] not in node:\n",
    "                    node[word[i]] = {}\n",
    "                node = node[word[i]]\n",
    "            node[\"#\"] = None\n",
    "        ans = 0\n",
    "        for word in words:\n",
    "            n = len(word)\n",
    "            node = trie\n",
    "            for i in range(n-1, -1,-1):\n",
    "                node = node[word[i]]\n",
    "            if len(node) == 1:\n",
    "                ans += len(word)+1\n",
    "                node[\"/\"] = None\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = {}\n",
    "        for x in words:\n",
    "            cur = trie\n",
    "            for i in range(len(x)-1, -1, -1):\n",
    "                if x[i] not in cur:\n",
    "                    cur[x[i]] = {}\n",
    "                cur = cur[x[i]]\n",
    "        res = 0\n",
    "        def count(trie, tmp):\n",
    "            nonlocal res\n",
    "            if not trie:\n",
    "                res += tmp+1\n",
    "            tmp += 1\n",
    "            for x in trie:\n",
    "                count(trie[x], tmp)\n",
    "        count(trie, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = list(set(words))\n",
    "\n",
    "        Trie = lambda : defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "\n",
    "        nodes = [reduce(dict.__getitem__, word[::-1], trie) for word in words]\n",
    "\n",
    "        return sum(len(words[i])+1 for i in range(len(words)) if len(nodes[i])==0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = {}\n",
    "        leng = 0\n",
    "        for word in words:\n",
    "            cur = trie\n",
    "            for i,ch in enumerate(word[::-1]):\n",
    "                if ch not in cur:\n",
    "                    leng += 1\n",
    "                    cur[ch] = {}\n",
    "                if '#' in cur:\n",
    "                    leng -= 1\n",
    "                    del cur['#']\n",
    "                \n",
    "                if i != 0 and len(cur) > 1 and cur[ch] == {}:\n",
    "                    leng += i\n",
    "                cur = cur[ch]\n",
    "            if not cur:\n",
    "                leng += 1\n",
    "                cur['#'] = {}\n",
    "            # print(leng)\n",
    "        return leng"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = {}\n",
    "        for word in words:\n",
    "            cur = trie\n",
    "            for c in word[::-1]:\n",
    "                if c not in cur:\n",
    "                    cur[c] = {}\n",
    "                cur = cur[c]\n",
    "            cur['#'] = {}\n",
    "        \n",
    "        self.res = 0\n",
    "        def dfs(node, cnt):\n",
    "            if '#' in node and len(node.keys()) == 1:\n",
    "                self.res += cnt + 1\n",
    "            for c in node:\n",
    "                if c == '#':\n",
    "                    continue\n",
    "                dfs(node[c], cnt+1)\n",
    "        dfs(trie, 0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = list(set(words)) #remove duplicates\n",
    "        #Trie is a nested dictionary with nodes created\n",
    "        # when fetched entries are missing\n",
    "        Trie = lambda: collections.defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "\n",
    "        #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]\n",
    "        nodes = [reduce(dict.__getitem__, word[::-1], trie)\n",
    "                 for word in words]\n",
    "\n",
    "        #Add word to the answer if it's node has no neighbors\n",
    "        return sum(len(word) + 1\n",
    "                   for i, word in enumerate(words)\n",
    "                   if len(nodes[i]) == 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words = list(set(words)) #remove duplicates\n",
    "        Trie = lambda: collections.defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "\n",
    "        nodes = [reduce(dict.__getitem__, word[::-1], trie)\n",
    "                 for word in words]\n",
    "        return sum(len(word) + 1\n",
    "                   for i, word in enumerate(words)\n",
    "                   if len(nodes[i]) == 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.trie_dict = dict()\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.answer = 0\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie_Trie = Trie()\n",
    "        for word in words:\n",
    "            pointer = trie_Trie\n",
    "            for letter in word[::-1]:\n",
    "                if letter not in pointer.trie_dict:\n",
    "                    pointer.trie_dict[letter] = Trie()\n",
    "                pointer = pointer.trie_dict[letter]\n",
    "        self.dfs(trie_Trie, 1)\n",
    "        return self.answer\n",
    "\n",
    "    def dfs(self, trie_Trie, level):\n",
    "        if len(trie_Trie.trie_dict) == 0:\n",
    "            self.answer += level\n",
    "            return\n",
    "        for key in trie_Trie.trie_dict.keys():\n",
    "            self.dfs(trie_Trie.trie_dict[key], level + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, val=None):\n",
    "        self.children = {}\n",
    "        self.val = val\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        head = Trie()\n",
    "        \n",
    "        for word in words:\n",
    "            cur = head\n",
    "            for c in word[::-1]:\n",
    "                if c not in cur.children:\n",
    "                    cur.children[c] = Trie(c)\n",
    "                cur = cur.children[c]\n",
    "        self.result = 0\n",
    "        def dfs(root, string):\n",
    "            if not root:\n",
    "                return\n",
    "                           \n",
    "            if root.children:\n",
    "                for key in root.children:\n",
    "                    dfs(root.children[key], string + key)\n",
    "            else:\n",
    "                self.result += len(string) + 1\n",
    "\n",
    "        for item in head.children:\n",
    "            dfs(head.children[item], item)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, val=None):\n",
    "        self.children = {}\n",
    "        self.val = val\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        head = Trie()\n",
    "        \n",
    "        for word in words:\n",
    "            cur = head\n",
    "            for c in word[::-1]:\n",
    "                if c not in cur.children:\n",
    "                    cur.children[c] = Trie(c)\n",
    "                cur = cur.children[c]\n",
    "        self.result = 0\n",
    "        def dfs(root, string):\n",
    "            if not root:\n",
    "                return\n",
    "                           \n",
    "            if root.children:\n",
    "                for key in root.children:\n",
    "                    dfs(root.children[key], string + key)\n",
    "            else:\n",
    "                self.result += len(string) + 1\n",
    "\n",
    "        for item in head.children:\n",
    "            dfs(head.children[item], item)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, val=None):\n",
    "        self.children = {}\n",
    "        self.val = val\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        head = Trie()\n",
    "        \n",
    "        for word in words:\n",
    "            cur = head\n",
    "            for c in word[::-1]:\n",
    "                if c not in cur.children:\n",
    "                    cur.children[c] = Trie(c)\n",
    "                cur = cur.children[c]\n",
    "        self.result = 0\n",
    "        def dfs(root, string):\n",
    "            if not root:\n",
    "                return\n",
    "                           \n",
    "            if root.children:\n",
    "                for key in root.children:\n",
    "                    dfs(root.children[key], string + key)\n",
    "            else:\n",
    "                self.result += len(string) + 1\n",
    "\n",
    "        for item in head.children:\n",
    "            dfs(head.children[item], item)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, val=None):\n",
    "        self.children = {}\n",
    "        self.val = val\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        head = Trie()\n",
    "        \n",
    "        for word in words:\n",
    "            cur = head\n",
    "            for c in word[::-1]:\n",
    "                if c not in cur.children:\n",
    "                    cur.children[c] = Trie(c)\n",
    "                cur = cur.children[c]\n",
    "        self.result = 0\n",
    "        def dfs(root, string):\n",
    "            if not root:\n",
    "                return\n",
    "                           \n",
    "            if root.children:\n",
    "                for key in root.children:\n",
    "                    dfs(root.children[key], string + key)\n",
    "            else:\n",
    "                self.result += len(string) + 1\n",
    "\n",
    "        for item in head.children:\n",
    "            dfs(head.children[item], item)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self):\n",
    "        self.child = dict()\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            curr = root\n",
    "            for ch in word[::-1]:\n",
    "                if ch not in curr.child:\n",
    "                    curr.child[ch] = Trie()\n",
    "                curr = curr.child[ch]\n",
    "        \n",
    "        res = []\n",
    "        def dfs(node, depth):\n",
    "            if not node.child:\n",
    "                res.append(depth)\n",
    "                return \n",
    "            \n",
    "            for i in node.child:\n",
    "                dfs(node.child[i], depth+1)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return sum(res) + len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"{self.children}\"\n",
    "\n",
    "    def insert(self, word):\n",
    "        if not word:\n",
    "            return\n",
    "\n",
    "        char = word[-1]\n",
    "        if char not in self.children:\n",
    "            self.children[char] = Trie()\n",
    "        self.children[char].insert(word[:-1])\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = Trie()\n",
    "\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        def walk(node, depth=0):\n",
    "            if not node.children:\n",
    "                nonlocal res\n",
    "                res += depth + 1\n",
    "                return\n",
    "\n",
    "            for child in node.children.values():\n",
    "                walk(child, depth + 1)\n",
    "\n",
    "        # print(trie)\n",
    "        walk(trie)\n",
    "        # print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self, val=None):\n",
    "        self.children = {}\n",
    "        self.val = val\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        head = Trie()\n",
    "        \n",
    "        for word in words:\n",
    "            cur = head\n",
    "            for c in word[::-1]:\n",
    "                if c not in cur.children:\n",
    "                    cur.children[c] = Trie(c)\n",
    "                cur = cur.children[c]\n",
    "        self.result = 0\n",
    "        def dfs(root, depth):\n",
    "            if not root:\n",
    "                return\n",
    "                           \n",
    "            if root.children:\n",
    "                for key in root.children:\n",
    "                    dfs(root.children[key], depth + 1)\n",
    "            else:\n",
    "                self.result += depth + 1\n",
    "\n",
    "        for item in head.children:\n",
    "            dfs(head.children[item], 1)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = {}\n",
    "        self.cnt = 0\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        cur = self\n",
    "        for w in word[::-1]: # 倒序遍历, 只有最后几位字母对齐, 才有复用的可能\n",
    "            if not cur.children.get(w):\n",
    "                cur.children[w] = Trie()\n",
    "                cur.cnt += 1\n",
    "            cur = cur.children[w]\n",
    "        cur.cnt += 1\n",
    "\n",
    "    def search(self, word: str) -> int:\n",
    "        cur = self\n",
    "        for w in word[::-1]:\n",
    "            if cur.children.get(w):\n",
    "                cur = cur.children[w]\n",
    "        return cur.cnt\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        t = Trie()\n",
    "        words = set(words) # 去重\n",
    "        for word in words:\n",
    "            t.insert(word)\n",
    "        res = 0\n",
    "        for word in words:\n",
    "            if t.search(word) == 1:\n",
    "                res += len(word) + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.child = {}\n",
    "        self.isend = False \n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self,word):\n",
    "        cur = self.root\n",
    "        for i in range(len(word)-1,-1,-1):\n",
    "            if word[i] not in cur.child:\n",
    "                cur.child[word[i]] = TrieNode()\n",
    "            cur = cur.child[word[i]]\n",
    "        cur.isend = True \n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        trie = Trie()\n",
    "        words = list(set(words))\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        \n",
    "        def find(word):\n",
    "            cur = trie.root\n",
    "            for i in range(len(word)-1,-1,-1):\n",
    "                cur = cur.child[word[i]]\n",
    "            if cur.child:\n",
    "                return True \n",
    "            return False  \n",
    "        \n",
    "        res = 0 \n",
    "        for word in words:\n",
    "            if not find(word):\n",
    "                res += len(word) + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "\n",
    "    def __init__(self) -> None:\n",
    "        self.content = [None] * 26\n",
    "\n",
    "def c2i(a):\n",
    "    return ord(a) - ord('a')\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.root = TreeNode()\n",
    "\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        \"\"\"\n",
    "        cur = self.root\n",
    "        for c in word:\n",
    "            i = c2i(c)\n",
    "            if cur.content[i] is None:\n",
    "                cur.content[i] = TreeNode()\n",
    "            cur = cur.content[i]\n",
    "    \n",
    "    def pathcount(self):\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(node, deep):\n",
    "            flag = True\n",
    "            for i in range(26):\n",
    "                if node.content[i]:\n",
    "                    dfs(node.content[i], deep+1)\n",
    "                    flag = False\n",
    "            if flag:\n",
    "                nonlocal ans\n",
    "                ans += deep\n",
    "\n",
    "        dfs(self.root, 1)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        tree = Trie()\n",
    "        for word in words:\n",
    "            tree.insert(word[::-1])\n",
    "        return tree.pathcount()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self) -> None:\n",
    "        self.children = [None] * 26\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        root = Trie()\n",
    "        for w in words:\n",
    "            cur = root\n",
    "            for c in w[::-1]:\n",
    "                idx = ord(c) - ord(\"a\")\n",
    "                if cur.children[idx] == None:\n",
    "                    cur.children[idx] = Trie()\n",
    "                cur = cur.children[idx]\n",
    "        return self.dfs(root, 1)\n",
    "\n",
    "    def dfs(self, cur: Trie, l: int) -> int:\n",
    "        isLeaf, ans = True, 0\n",
    "        for i in range(26):\n",
    "            if cur.children[i] != None:\n",
    "                isLeaf = False\n",
    "                ans += self.dfs(cur.children[i], l + 1)\n",
    "        if isLeaf:\n",
    "            ans += l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.tree=[None]*26\n",
    "        self.is_end=False\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self,words) -> int:\n",
    "        node1 = Trie()\n",
    "        words.sort(key=lambda x: -len(x))\n",
    "        result = []\n",
    "\n",
    "        for word in words:\n",
    "            node=node1\n",
    "            sign = False\n",
    "            for w in word[::-1]:\n",
    "                index = ord(w) - ord('a')\n",
    "                if not node.tree[index]:\n",
    "                    sign = True\n",
    "                    node.tree[index] = Trie()\n",
    "                node = node.tree[index]\n",
    "            if sign:\n",
    "                result.append(word)\n",
    "\n",
    "        a='#'.join(result)\n",
    "        b=len(a)+1\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children=[None]*26\n",
    "        self.ifword=False\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words) -> int:\n",
    "        head=Node()\n",
    "        res=0\n",
    "        words=sorted(words,key=lambda x:len(x),reverse=True)\n",
    "        for word in words:\n",
    "            ptr=head\n",
    "            word=\"\".join(reversed(word))\n",
    "            for i in range(len(word)):\n",
    "                if ptr.children[ord(word[i])-ord('a')]==None:\n",
    "                    for j in range(i,len(word)):\n",
    "                        ptr.children[ord(word[j])-ord('a')]=Node()\n",
    "                        ptr=ptr.children[ord(word[j])-ord('a')]\n",
    "                    ptr.ifword=True\n",
    "                    res=res+len(word)+1\n",
    "                    break\n",
    "                ptr=ptr.children[ord(word[i])-ord('a')]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "\n",
    "    def insert(self, w):\n",
    "        node = self\n",
    "        pref = True\n",
    "        for c in w:\n",
    "            idx = ord(c) - ord(\"a\")\n",
    "            if node.children[idx] is None:\n",
    "                node.children[idx] = Trie()\n",
    "                pref = False\n",
    "            node = node.children[idx]\n",
    "        return 0 if pref else len(w) + 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda x: -len(x))\n",
    "        trie = Trie()\n",
    "        return sum(trie.insert(w[::-1]) for w in words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.child = [None] * 26\n",
    "        self.is_word = False\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        cur_node, n = self.root, len(word)\n",
    "        for i in range(n):\n",
    "            if not cur_node.child[ord(word[i]) - ord('a')]:\n",
    "                new_node = TrieNode()\n",
    "                cur_node.child[ord(word[i]) - ord('a')] = new_node\n",
    "                cur_node = new_node\n",
    "            else:\n",
    "                cur_node = cur_node.child[ord(word[i]) - ord('a')]            \n",
    "            if i == n - 1: \n",
    "                cur_node.is_word = True\n",
    "\n",
    "    def _searchPrefix(self, prefix):\n",
    "        cur_node = self.root\n",
    "        for char in prefix:\n",
    "            if cur_node.child[ord(char) - ord('a')]:\n",
    "                cur_node = cur_node.child[ord(char) - ord('a')]\n",
    "            else:\n",
    "                return None\n",
    "        return cur_node\n",
    "\n",
    "    def searchWord(self, word: str) -> bool:\n",
    "        search_ = self._searchPrefix(word)\n",
    "        return True if search_ and search_.is_word == True else False\n",
    "\n",
    "    def searchPrefix(self, prefix: str) -> bool:\n",
    "        return True if self._searchPrefix(prefix) else False\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "\n",
    "        \n",
    "        for i, word in enumerate(words):\n",
    "            words[i] = word[::-1]\n",
    "        words.sort(key = lambda x: -len(x))\n",
    "\n",
    "        T, ans = Trie(), 0\n",
    "        for word in words:\n",
    "            if not T.searchPrefix(word):\n",
    "                T.insert(word)\n",
    "                ans += len(word) + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children=[None]*26\n",
    "        self.ifword=False\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words) -> int:\n",
    "        head=Node()\n",
    "        res=0\n",
    "        words=sorted(words,key=lambda x:len(x),reverse=True)\n",
    "        for word in words:\n",
    "            ptr=head\n",
    "            word=\"\".join(reversed(word))\n",
    "            for i in range(len(word)):\n",
    "                if ptr.children[ord(word[i])-ord('a')]==None:\n",
    "                    for j in range(i,len(word)):\n",
    "                        ptr.children[ord(word[j])-ord('a')]=Node()\n",
    "                        ptr=ptr.children[ord(word[j])-ord('a')]\n",
    "                    ptr.ifword=True\n",
    "                    res=res+len(word)+1\n",
    "                    break\n",
    "                ptr=ptr.children[ord(word[i])-ord('a')]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            trie.insert(word)\n",
    "        return trie.res\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None for _ in range(26)]\n",
    "        self.isEnd = False\n",
    "        self.res = 0\n",
    "\n",
    "    def insert(self, word):\n",
    "        node = self\n",
    "        cnt = 0\n",
    "        for i in range(len(word) - 1, -1, -1):\n",
    "            ch = ord(word[i]) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "            cnt += 1\n",
    "            if node.isEnd:\n",
    "                node.isEnd = False\n",
    "                self.res -= (cnt + 1)\n",
    "        node.isEnd = True\n",
    "        self.res += cnt + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "\n",
    "        self.child = [None for _ in range(26)]\n",
    "\n",
    "        self.cnt = 0        #经过这个结点的单词个数\n",
    "\n",
    "\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "\n",
    "        root = self\n",
    "\n",
    "        for c in word[::-1]:\n",
    "\n",
    "            ID = ord(c) - ord('a')\n",
    "\n",
    "            if root.child[ID] == None:\n",
    "\n",
    "                root.child[ID] = Trie()\n",
    "\n",
    "                root.cnt += 1\n",
    "\n",
    "            root = root.child[ID]\n",
    "\n",
    "        root.cnt += 1\n",
    "\n",
    "\n",
    "\n",
    "    def search(self, word: str) -> int:\n",
    "\n",
    "        root = self\n",
    "\n",
    "        for c in word[::-1]:\n",
    "\n",
    "            ID = ord(c) - ord('a')\n",
    "\n",
    "            root = root.child[ID]\n",
    "\n",
    "        return root.cnt \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        # if len(words)==0:\n",
    "        #     return 0\n",
    "        # #\n",
    "        # words = list(set(words))\n",
    "        # temp_words = copy.deepcopy(words)\n",
    "        # words_n = len(words)\n",
    "        # for i in range(words_n):\n",
    "        #     now_word = words[i]\n",
    "        #     for j in range(len(temp_words)):\n",
    "        #         if now_word in temp_words[j] and now_word ==temp_words[j][-len(now_word):] and now_word != temp_words[j]:\n",
    "        #             # print(now_word,'temp_words[j][-len(now_word):]-',temp_words[j][-len(now_word):])\n",
    "        #             temp_words.remove(now_word)\n",
    "        #             break\n",
    "        #     #\n",
    "        # #\n",
    "        # s =\"\"\n",
    "        # for word in temp_words:\n",
    "        #     s+=word +\"#\"\n",
    "        # return len(s)\n",
    "\n",
    "        T = Trie()\n",
    "\n",
    "\n",
    "\n",
    "        words_us = set(words)\n",
    "\n",
    "\n",
    "\n",
    "        for word in words_us:\n",
    "\n",
    "            T.insert(word)\n",
    "\n",
    "        \n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for word in words_us:\n",
    "\n",
    "            if T.search(word) == 1:       #是Trie树里一条路径最长的那个单词\n",
    "\n",
    "                res += len(word) + 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children=[None]*26\n",
    "        self.ifword=False\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words) -> int:\n",
    "        head=Node()\n",
    "        res=0\n",
    "        for word in words:\n",
    "            ptr=head\n",
    "            word=\"\".join(reversed(word))\n",
    "            for i in range(len(word)):\n",
    "                if ptr.children[ord(word[i])-ord('a')]==None:\n",
    "                    if ptr.ifword==True:\n",
    "                        if i==len(word)-1:\n",
    "                            ptr.ifword=False\n",
    "                        res = res + len(word)-i\n",
    "                    else:\n",
    "                        res = res + len(word) + 1\n",
    "                    for j in range(i,len(word)):\n",
    "                        ptr.children[ord(word[j])-ord('a')]=Node()\n",
    "                        ptr=ptr.children[ord(word[j])-ord('a')]\n",
    "                    ptr.ifword=True\n",
    "                    break\n",
    "                ptr=ptr.children[ord(word[i])-ord('a')]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.children = [None]*26\n",
    "        self.isEnd = False\n",
    "\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        \"\"\"\n",
    "        Inserts a word into the trie.\n",
    "        \"\"\"\n",
    "        node = self\n",
    "        for w in word:\n",
    "            i = ord(w) - ord(\"a\")\n",
    "            if not node.children[i]:\n",
    "                node.children[i] = Trie()\n",
    "            node = node.children[i]\n",
    "        node.isEnd = True\n",
    "        \n",
    "\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        \"\"\"\n",
    "        Returns if the word is in the trie.\n",
    "        \"\"\"\n",
    "        node = self\n",
    "        for w in word:\n",
    "            i = ord(w) - ord(\"a\")\n",
    "            if node.children[i]:\n",
    "                node = node.children[i]\n",
    "            else:\n",
    "                return False\n",
    "        if node.isEnd:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        \"\"\"\n",
    "        Returns if there is any word in the trie that starts with the given prefix.\n",
    "        \"\"\"\n",
    "        node = self\n",
    "        for w in prefix:\n",
    "            i = ord(w) - ord(\"a\")\n",
    "            if node.children[i]:\n",
    "                node = node.children[i]\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        # 先将words 按从大到小排序\n",
    "        words = [word[::-1] for word in words]\n",
    "        words.sort(reverse=True)\n",
    "        print(\"words = \", words)\n",
    "        trie = Trie()\n",
    "        indices = []\n",
    "        s = \"\"\n",
    "        # longgerWord = \"\"\n",
    "        for i in range(len(words)):\n",
    "            word = words[i]\n",
    "            if not trie.startsWith(word):\n",
    "                # longgerWord = word\n",
    "                s = s + word[::-1]+\"#\"\n",
    "                indices.append(len(s))\n",
    "                trie.insert(word)\n",
    "            else:\n",
    "                indices.append(len(s)-len(word)-1)\n",
    "        print(\"s = \", s)\n",
    "        return len(s)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.tree=[None]*26\n",
    "        self.is_end=False\n",
    "\n",
    "    def insert(self,word):\n",
    "        node=Trie()\n",
    "        for w in word:\n",
    "            index=ord(w)-ord('a')\n",
    "            if not node.tree[index]:\n",
    "                node.tree[index]=Trie()\n",
    "            node=node.tree[index]\n",
    "        node.is_end=True\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self,words) -> int:\n",
    "        node1 = Trie()\n",
    "        words.sort(key=lambda x: -len(x))\n",
    "        result = []\n",
    "\n",
    "        for word in words:\n",
    "            node=node1\n",
    "            sign = False\n",
    "            for w in word[::-1]:\n",
    "                index = ord(w) - ord('a')\n",
    "                if not node.tree[index]:\n",
    "                    sign = True\n",
    "                    node.tree[index] = Trie()\n",
    "                node = node.tree[index]\n",
    "            if sign:\n",
    "                result.append(word)\n",
    "\n",
    "        a='#'.join(result)\n",
    "        b=len(a)+1\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "        def __init__(self,):\n",
    "            self.child = [None] * 26\n",
    "            self.isEnd = False\n",
    "\n",
    "class Solution:\n",
    "    def minimumLengthEncoding(self, words: List[str]) -> int:\n",
    "        '''\n",
    "            目标转化为求公共后缀，即如果该字符串a为另一字符串b的后缀，则a可以借用b来表示\n",
    "            所以我们只要将后缀字符串通通合并，剩余字符串的数量（#的个数）+ 字符串总长度即为所求\n",
    "        '''\n",
    "        root = Trie()\n",
    "        merged = set() #\n",
    "        for word in words:\n",
    "            curr = root\n",
    "            for i in range(len(word)-1, -1, -1):\n",
    "                ch = ord(word[i]) - ord('a')\n",
    "                if not curr.child[ch]:\n",
    "                    curr.child[ch] = Trie()\n",
    "                if curr.isEnd:\n",
    "                    curr.isEnd = False\n",
    "                    merged.remove(word[i+1:len(word)])\n",
    "                curr = curr.child[ch]\n",
    "            for node in curr.child:\n",
    "                if node: break\n",
    "            else:\n",
    "                curr.isEnd = True\n",
    "                merged.add(word)\n",
    "        n = sum(len(word) for word in merged)\n",
    "        return len(merged) + n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
